package com.leetcode.partition6;

import com.leetcode.common.TreeNode;

/**
 * @author `RKC`
 * @date 2021/8/18 10:14
 */
public class LC572另一个树的子树 {

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        return recursion(root, subRoot);
    }

    public static void main(String[] args) {
        TreeNode r1 = new TreeNode(3, new TreeNode(4, null, new TreeNode(2)), new TreeNode(5));
        TreeNode r2 = new TreeNode(4, new TreeNode(1), new TreeNode(2));
        System.out.println(new LC572另一个树的子树().isSubtree(r1, r2));
    }

    private boolean recursion(TreeNode root, TreeNode subRoot) {
        if (root == null) return false;
        if (root.val == subRoot.val) {
            if (isSameTree(root, subRoot)) return true;
            return recursion(root.left, subRoot) || recursion(root.right, subRoot);
        }
        return recursion(root.left, subRoot) || recursion(root.right, subRoot);
    }

    private boolean isSameTree(TreeNode root, TreeNode subRoot) {
        if ((root == null && subRoot != null) || (root != null && subRoot == null)) return false;
        if (root == null) return true;
        if (root.val != subRoot.val) return false;
        return isSameTree(root.left, subRoot.left) && isSameTree(root.right, subRoot.right);
    }
}
